package com.captain.leetcode;

import java.util.Arrays;

/**
 * @author captain
 * @Des给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 示例 1:
 * <p>
 * 输入: num1 = "2", num2 = "3"
 * 输出: "6"
 * 示例 2:
 * <p>
 * 输入: num1 = "123", num2 = "456"
 * 输出: "56088"
 * 说明：
 * <p>
 * num1 和 num2 的长度小于110。
 * num1 和 num2 只包含数字 0-9。
 * num1 和 num2 均不以零开头，除非是数字 0 本身。
 * 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
 */
public class 字符串相乘43 {

    public static void main(String[] args) {
        System.out.println(multiply("99", "99"));
    }

    public static String multiply(String num1, String num2) {
        //  19  num1
        //  46  num2
        //  54  i+j
        //  6
        // 114  [][][][]
        // 36
        // 474
        // 4
        // 874
        //
        //      81

        if (("0").equals(num1) | ("0").equals(num2)) {
            return "0";
        }

        int m = num1.length();
        int n = num2.length();
        int[] res = new int[m + n];

        for (int j = n - 1; j >= 0; j--) {
            for (int i = m - 1; i >= 0; i--) {
                //(√)
                int num = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int p1 = i + j;
                int p2 = i + j + 1;
                int sum = num + res[p2];
                res[p2] = sum % 10;
                //此处的+=是为了处理进位用的，例如19*19，列出竖式看一下就知道了。
                res[p1] += sum / 10;
                System.out.println(Arrays.toString(res));
            }
        }
        StringBuilder resBuilder = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            //首位为0,排除
            if (res[i] == 0 && i == 0) {
                continue;
            }
            resBuilder.append(res[i]);
        }
        return resBuilder.toString();
    }
}
